package mo.leetcode_top;

public class L215 {

    public int findKthLargest(int[] nums, int k) {
        int left = 0;
        int right = nums.length - 1;
        while (true) {
            int position = partition(nums, left, right);
            if (position == k - 1) {
                return nums[position];
            }
            if (position > k-1) {
                right = position - 1;
            } else {
                left = position + 1;
            }
        }
    }


    private int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int l = left + 1;
        int r = right;
        while (l <= r) {
            if (nums[l] < pivot && nums[r] > pivot) {
                swap(l, r, nums);
                l++;
                r--;
            }
            if (nums[l] >= pivot) {
                l++;
            }
            if (nums[r] <= pivot) {
                r--;
            }
        }
        swap(left, r, nums);
        return r;
    }


    private void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
